#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>//rand()
#define rep(i,a,b) for(register int i = (a);i <= (b);++i)
#define per(i,a,b) for(register int i = (a);i >= (b);--i)
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
using std::map;

map<ll,ll> mp;
ll a,b,c,d,T,N;

inline ll dfs(ll n){
    if(mp.count(n)) return mp[n];
    if(n == 0) return 0;
    if(n == 1) return d;
    ll tmp = 0x7f7f7f7f7f7f7f7f;
    if(n < tmp / d) tmp = n * d;
    ll a1 = n/2*2 , a2 = (n+1)/2*2;
    ll b1 = n/3*3 , b2 = (n+2)/3*3;
    ll c1 = n/5*5 , c2 = (n+4)/5*5;
    tmp = std::min(tmp,a + dfs(a1/2) + d * std::abs(a1-n)),
    tmp = std::min(tmp,a + dfs(a2/2) + d * std::abs(a2-n)),
    tmp = std::min(tmp,b + dfs(b1/3) + d * std::abs(b1-n)),
    tmp = std::min(tmp,b + dfs(b2/3) + d * std::abs(b2-n)),
    tmp = std::min(tmp,c + dfs(c1/5) + d * std::abs(c1-n)),
    tmp = std::min(tmp,c + dfs(c2/5) + d * std::abs(c2-n));
    mp[n] = tmp;
    return tmp;
}

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.in", "r", stdin);
    cin >> T;
    while(T--){
        mp.clear();
        cin >> N >> a >> b >> c >> d;
        cout << dfs(N) << "\n";
    }
    return 0;
}